package gold.digger;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC51 {

    /*
     * @param 此题目直接用别人代码，自己只理解思想
     * @return:
     */
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        List<String> queen = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(".");
        }

        for (int i = 0; i < n; i++) {
            queen.add(sb.toString());
        }

        helper(0, queen, res);
        return res;
    }

    public void helper(int curRow, List<String> queens, List<List<String>> res) {
        int n = queens.size();
        if (curRow == n) {
            res.add(deepCopy(queens));
            return;
        }
        for (int i = 0; i < n; ++i) {
            if (isValid(queens, curRow, i)) {
                StringBuilder strBuilder = new StringBuilder(queens.get(curRow));
                strBuilder.setCharAt(i, 'Q');
                queens.set(curRow, strBuilder.toString());
                helper(curRow + 1, queens, res);

                strBuilder = new StringBuilder(queens.get(curRow));
                strBuilder.setCharAt(i, '.');
                queens.set(curRow, strBuilder.toString());
            }
        }
    }

    public List<String> deepCopy(List<String> list) {
        List<String> copyList = new ArrayList<>();
        for (String el : list) {
            copyList.add(new String(el));
        }

        return copyList;
    }

    public boolean isValid(List<String> puzzle, int row, int col) {
        for (int i = 0; i < row; ++i) {
            if (puzzle.get(i).charAt(col) == 'Q') return false;
        }
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) {
            if (puzzle.get(i).charAt(j) == 'Q') return false;
        }
        for (int i = row - 1, j = col + 1; i >= 0 && j < puzzle.size(); --i, ++j) {
            if (puzzle.get(i).charAt(j) == 'Q') return false;
        }
        return true;
    }


    public static void main(String[] args) {
        LC51 an = new LC51();
        System.out.println(an.solveNQueens(4));
    }
}
